package datastructure.map;

import datastructure.set.HashSet;
import datastructure.set.Set;

import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * Description：
 * Author: zhangc
 * Date：2017/7/22 15:19
 */
public class HashMap<K, V> implements Map<K, V>, Iterable<Map.Entry<K, V>> {

    private int CAPACITY = 1 << 4;
    private int size = 0;
    private final double FACTORY = 0.75;

    private Entry<K, V>[] entrys;

    public HashMap() {
        entrys = new Entry[ CAPACITY ];
    }

    @Override
    public boolean put(K key, V value) {
        if (CAPACITY * FACTORY < size)
            enLargeSize();
        if (!containsKey(key)) {
            Entry<K, V> entry = new Entry<>(key, value);
            linkNode(entrys, entry, getIndex(key));
            ++size;
            return true;
        } else {
            Entry<K, V> entry = getEntry(key);
            entry.value = value;
            return false;
        }
    }

    private static <K, V> void linkNode(Entry<K, V>[] entrys, Entry<K, V> entry, int index) {
        if (entrys[ index ] == null) {
            entrys[ index ] = entry;
            entrys[ index ].next = null;
        } else {
            Entry<K, V> temp = entrys[ index ];
            entry.next = temp.next;
            temp.next = entry;
        }
    }


    private void enLargeSize() {
        CAPACITY = CAPACITY + (CAPACITY >> 1);
        Entry<K, V>[] newEntry = new Entry[ CAPACITY ];
        Entry<K, V> entry;
        Entry<K, V> temp;
        for (int i = 0; i < entrys.length; i++) {
            entry = entrys[ i ];
            while (entry != null) {
                temp = entry.next;
                linkNode(newEntry, entry, getIndex(entry.key));
                entry = temp;
            }
        }
        entrys = newEntry;
    }

    @Override
    public V get(K key) {
        if (containsKey(key)) {
            return getEntry(key).value;
        }
        throw new NoSuchElementException("map 中无此元素");
    }

    @Override
    public boolean containsKey(K key) {
        int hash = hash(key);
        int index = getIndex(key);
        if (entrys[ index ] == null)
            return false;
        Entry<K, V> temp = entrys[ index ];
        while (temp != null) {
            if (temp.hash == hash)
                return true;
            temp = temp.next;
        }
        return false;
    }

    public Entry<K, V> getEntry(K key) {
        int hash = hash(key);
        int index = getIndex(key);
        Entry<K, V> temp = entrys[ index ];
        while (temp != null) {
            if (temp.hash == hash)
                return temp;
            temp = temp.next;
        }
        return null;
    }

    @Override
    public boolean containsValue(V value) {
        return false;
    }

    @Override
    public void remove(K key) {
        if (!containsKey(key))
            throw new NoSuchElementException("map 中无此元素");
        int index = getIndex(key);
        int hash = hash(key);
        if (entrys[ index ].hash == hash)
            entrys[ index ] = entrys[ index ].next;
        else {
            Entry<K, V> entry = entrys[ index ];
            while (entry.next.hash != hash) {
                entry = entry.next;
            }
            entry.next = entry.next.next;
        }
        size--;
    }

    @Override
    public boolean isEmpty() {
        return size <= 0;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public Set<Map.Entry<K, V>> entrySet() {
        Set<Map.Entry<K, V>> set = new HashSet<>();
        Entry<K, V> entry;
        for (int i = 0; i < entrys.length; i++) {
            entry = entrys[ i ];
            while (entry != null) {
                set.add(entry);
                entry = entry.next;
            }
        }
        return set;
    }

    @Override
    public Set<K> keySet() {
        Set<K> set = new HashSet<>();
        Iterator<Map.Entry<K, V>> iterator = entrySet().iterator();
        while (iterator.hasNext())
            set.add(iterator.next().getKey());
        return set;
    }

    private int getIndex(K key) {
        int hash = Math.abs(hash(key));
        return hash % CAPACITY;
    }

    public static class Entry<K, V> implements Map.Entry<K, V> {

        private K key;
        private V value;
        private int hash;

        Entry<K, V> next;

        public Entry(K key, V value) {
            this.key = key;
            this.value = value;
            this.hash = hash(key);
        }

        @Override
        public K getKey() {
            return key;
        }

        @Override
        public V getValue() {
            return value;
        }

        @Override
        public void setValue(V value) {
            this.value = value;
        }

        @Override
        public int hashcode() {
            return hash(key);
        }

        @Override
        public boolean equals(Map.Entry<K, V> entry) {
            return hash == hash(entry);
        }

    }

    private static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

    @Override
    public Iterator<Map.Entry<K, V>> iterator() {
        return new MapItr();
    }

    public class MapItr implements Iterator<Map.Entry<K, V>> {
        Entry<K, V> currentNode;
        int currentNum = 0;
        int currentSlot = 0;

        @Override
        public boolean hasNext() {
            return currentNum < size;
        }

        @Override
        public Entry<K, V> next() {
            if (currentNode == null) {
                for (int i = currentSlot; i < CAPACITY; i++) {
                    if (entrys[ i ] != null) {
                        currentNode = entrys[ i ];
                        currentNum++;
                        currentSlot = i;
                        break;
                    }
                }
            } else {
                if (currentNode.next != null) {
                    currentNode = currentNode.next;
                    ++currentNum;
                } else {
                    for (int i = currentSlot + 1; i < CAPACITY; i++) {
                        if (entrys[ i ] != null) {
                            currentNode = entrys[ i ];
                            currentNum++;
                            currentSlot = i;
                            break;
                        }
                    }
                }
            }
            return currentNode;
        }
    }

}
